package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 基于最小堆的优先队列
 * 
 * @author 付大石
 */
public class MinPQ<T extends Comparable<T>> {

    /**
     * 优先队列
     */
    private T[] pq;

    /**
     * 元素个数
     */
    private int size;

    private static final int INIT_CAPACITY = 10;

    public MinPQ() {
        pq = (T[]) new Comparable[INIT_CAPACITY + 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(T item) {

        if (size + 1 >= pq.length) {
            resize(pq.length * 2);
        }
        pq[++size] = item;
        swim(size);
    }

    private void resize(int newCapacity) {

        if (newCapacity < INIT_CAPACITY) {
            return;
        }

        T[] tempPQ = (T[]) new Comparable[newCapacity];
        for (int i = 1; i <= size; i++) {
            tempPQ[i] = pq[i];
        }
        pq = tempPQ;
    }

    public T delMin() {

        T min = min();
        swap(1, size);
        size--;
        sink(1);
        if (size * 4 < pq.length) {
            resize(pq.length / 2);
        }
        return min;

    }

    public T min() {
        if (isEmpty()) {
            throw new RuntimeException("优先队列已空");
        }
        return pq[1];
    }

    private void sink(int k) {

        T target = pq[k];
        while (2 * k <= size) {
            int i = 2 * k;
            if (2 * k + 1 <= size && pq[i].compareTo(pq[i + 1]) > 0) { // 找出两个叶子节点中较小的一个
                i++;
            }
            if (target.compareTo(pq[i]) < 0) {
                break;
            }
            pq[k] = pq[i];
            k = i;
        }
        pq[k] = target;
    }

    private void swim(int k) {

        T target = pq[k];
        while (k > 1 && target.compareTo(pq[k / 2]) < 0) { // 子节点比父节点更小，上浮
            pq[k] = pq[k / 2];
            k = k / 2;
        }
        pq[k] = target;
    }

    private void swap(int i, int j) {

        T temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }
}
